Section: Application Domains

Recherche opérationnelle/Operations research

L'algèbre max-plus intervient de plusieurs manières en Recherche opérationnelle. Premièrement, il existe des liens profonds entre l'algèbre max-plus et les problèmes d'optimisation discrète, voir  [95] . Ces liens conduisent parfois à de nouveaux algorithmes pour les problèmes de recherche opérationnelle classiques, comme le problème de circuit de poids moyen maximum  [104] . Certains problèmes combinatoires, comme des problèmes de programmation disjonctive, peuvent être décomposés par des méthodes de type max-plus  [184] . Ensuite, le rôle de l'algèbre max-plus dans les problèmes d'ordonnancement est bien connu depuis les années 60, les dates de complétion pouvant souvent être calculées à partir d'équations linéaires max-plus. Plus récemment, des représentations de problèmes d'ordonnancement ont pu être obtenues à partir de semi-groupes de matrices max-plus : une première représentation a été obtenue dans  [126] pour le cas du “jobshop”, une représentation plus simple a été obtenue dans  [147] dans le cas du “flowshop”. Ce point de vue algébrique a été très utile dans le cas du “flowshop” : il permet de retrouver des résultats anciens de dominance et d'obtenir ainsi de nouvelles bornes  [147] . Finalement, en regardant l'algèbre max-plus comme une limite de l'algèbre classique, on peut utiliser des outils algébriques en optimisation combinatoire  [144] .

English version

Max-plus algebra arise in several ways in Operations Research. First, there are intimate relations between max-plus algebra and discrete optimisation problems, see  [95] . Sometimes, these relations lead to new algorithms for classical Operations Research problems, like the maximal circuit mean  [104] . There are also special combinatorial problems, like certain problems of disjunctive programming, which can be decomposed by max-plus type methods  [184] . Next, the role of max-plus algebra in scheduling problems has been known since the sixties: completion dates can often be computed by max-plus linear equations. Recently, representations of certain scheduling problems using max-plus matrix semigroups have appeared, a first representation was given in  [126] for the jobshop case, a simpler representation was given in  [147] in the flowshop case. This algebraic point of view turned out to be particularly fruitful in the flowshop case: it allows one to recover old dominance results and to obtain new bounds  [147] . Finally, viewing max-plus algebra as a limit of classical algebra allows to use algebraic tools in combinatorial optimisation  [144] .